package 典型.动态规划;

public class Bag01 {
    // 一般解法 （返回了装入背包的所有编号）
    public static String ZeroOnePack(int V,int N,int[] weight,int[] value){
        //初始化动态规划数组.dp[i][j]表示背包容量为j时，使用i种商品的最大价值
        int[][] dp = new int[N+1][V+1];
        for(int i=1;i<N+1;i++){
            for(int j=1;j<V+1;j++){
                //如果第i件物品的重量大于背包容量j,则不装入背包
                if(weight[i-1] > j) dp[i][j] = dp[i-1][j];
                else dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]);
            }
        }
        //则容量为V的背包能够装入物品的最大值为
        int maxValue = dp[N][V];
        //逆推找出装入背包的所有商品的编号
        return getString(V, N, weight, dp);
    }

    // 优化解法 (返回了最大价值)
    public static int ZeroOnePack2(int V,int N,int[] weight,int[] value){
        //动态规划
        int[] dp = new int[V+1];
        for(int i=1;i<N+1;i++){
            //逆序实现，之前访问过的背包不会再次访问
            for(int j=V;j>=weight[i-1];j--){
                dp[j] = Math.max(dp[j-weight[i-1]]+value[i-1],dp[j]);
            }
        }
        return dp[V];
    }

    private static String getString(int V, int N, int[] weight, int[][] dp) {
        int j= V;
        StringBuilder numStr= new StringBuilder();
        for(int i = N; i>0; i--){
            //若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
            if(dp[i][j]> dp[i-1][j]){
                numStr.insert(0, i + " ");
                j=j- weight[i-1];
            }
            if(j==0)
                break;
        }
        return numStr.toString();
    }


}
